import java.util.ArrayList;
import java.util.List;

public class question_17 {
}
class Solution_17 {
    public List<String> dfs(char arr[][],char err[],List<String> result,char orr[],int n){
        /*
        * arr是二维数组表，用来存放数字与字母之间的映射关系
        * err是用来存放某一具体结果的数组，最后要将这个字符数组转化成字符串，存入到结果集合中去
        * orr是用来存放digits字符串转化而成的字符数组，里面存的是数字，可以通过里面的数字映射到对应的二维数组
        *
        */
        if(n==orr.length)
            return result;
        int temp=(orr[n])-48-2;
        for (int i = 0; i < arr[temp].length; i++) {
            err[n]=arr[temp][i];
            if(n==orr.length){
                String s = new String(err);
                result.add(s);
            }
            //继续递归
            dfs(arr,err,result,orr,n+1);
        }
        return result;
    }
    public List<String> letterCombinations(String digits) {
        if(digits==null||digits.length()==0)
            return new ArrayList<String>();
        //先建立一个二维数组对数字与字母之间的关系进行映射
        char arr[][]=new char[8][];
        ArrayList<String> result = new ArrayList<>();
        arr[0]= new char[]{'a', 'b', 'c'};
        arr[1]= new char[]{'d', 'e', 'f'};
        arr[2]= new char[]{'g', 'h', 'i'};
        arr[3]= new char[]{'j', 'k', 'l'};
        arr[4]= new char[]{'m', 'n', 'o'};
        arr[5]= new char[]{'p', 'q', 'r','s'};
        arr[6]= new char[]{'t', 'u', 'v'};
        arr[7]= new char[]{'w', 'x', 'y','z'};
        //先将digits转化成字符数组
        char[] orr = digits.toCharArray();
        char[] err = new char[digits.length()];
        int n=0;
        return dfs(arr,err,result,orr,0);
    }
}
